{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Subarrays With Score Less Than K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计得分小于 K 的子数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个数组的 <strong>分数</strong>&nbsp;定义为数组之和 <strong>乘以</strong>&nbsp;数组的长度。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>[1, 2, 3, 4, 5]</code>&nbsp;的分数为&nbsp;<code>(1 + 2 + 3 + 4 + 5) * 5 = 75</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个正整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，请你返回&nbsp;<code>nums</code>&nbsp;中分数&nbsp;<strong>严格小于&nbsp;</strong><code>k</code>&nbsp;的&nbsp;<strong>非空整数子数组数目</strong>。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中的一个连续元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,4,3,5], k = 10\n",
    "<b>输出：</b>6\n",
    "<strong>解释：</strong>\n",
    "有 6 个子数组的分数小于 10 ：\n",
    "- [2] 分数为 2 * 1 = 2 。\n",
    "- [1] 分数为 1 * 1 = 1 。\n",
    "- [4] 分数为 4 * 1 = 4 。\n",
    "- [3] 分数为 3 * 1 = 3 。 \n",
    "- [5] 分数为 5 * 1 = 5 。\n",
    "- [2,1] 分数为 (2 + 1) * 2 = 6 。\n",
    "注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1], k = 5\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>\n",
    "除了 [1,1,1] 以外每个子数组分数都小于 5 。\n",
    "[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。\n",
    "所以总共有 5 个子数组得分小于 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>15</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-subarrays-with-score-less-than-k](https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-subarrays-with-score-less-than-k](https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4,3,5]\\n10', '[1,1,1]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        window = 0 \n",
    "        s = 0 \n",
    "        l = r = 0 \n",
    "        ans = 0 \n",
    "        while r < len(nums):\n",
    "            num =  nums[r] \n",
    "            s += nums[r]\n",
    "\n",
    "            while s* (r-l+1) >= k :\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            r += 1\n",
    "            ans += r - l \n",
    "\n",
    "        return ans \n",
    "\n",
    "#\n",
    "\n",
    "\n",
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left,right = 0,0\n",
    "        res = 0\n",
    "        window = 0\n",
    "        # 正常滑动窗口都是找出最大/长的子数组，故res不可以只是+=1，而是要+=right-left\n",
    "        # 而是要判断，在这题中只要某个子数组满足题目要求，在该子数组内的更短的子数组同样也满足题目要求。\n",
    "        while right < n:\n",
    "            window += nums[right]\n",
    "            while window * (right - left + 1) >= k:\n",
    "                window -= nums[left]\n",
    "                left += 1\n",
    "            right += 1\n",
    "            res += right - left  \n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        res = s = left = 0\n",
    "        for right,num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        s = 0 \n",
    "        l = r = 0 \n",
    "        ans = 0 \n",
    "        while r < len(nums):\n",
    "            s += nums[r]\n",
    "            r += 1\n",
    "            while s* (r-l) >= k :\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            ans += r - l \n",
    "\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        i = s = ans = 0\n",
    "        for j,v in enumerate(nums):\n",
    "            s += v\n",
    "            while s * (j-i+1) >= k:\n",
    "                s -= nums[i]\n",
    "                i += 1\n",
    "            ans += j-i+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        l = 0\n",
    "        # 枚举右边界\n",
    "        for r, x in enumerate(nums):\n",
    "            cur += x\n",
    "            # 找出最大滑窗(最靠左的左边界), 再小都满足了\n",
    "            while cur * (r - l + 1) >= k:\n",
    "                cur -= nums[l]\n",
    "                l += 1\n",
    "            # 从l到r的左边界都满足题意\n",
    "            if cur * (r - l + 1) < k:\n",
    "                ans += (r - l + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = sm = 0\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            sm += x\n",
    "            while sm * (r - l + 1) >= k:\n",
    "                sm -= nums[l]\n",
    "                l += 1\n",
    "            ans += (r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        current_sum = 0\n",
    "        while r < len(nums):\n",
    "            current_sum += nums[r]\n",
    "            while current_sum * (r - l + 1) >= k:\n",
    "                current_sum -= nums[l]\n",
    "                l += 1\n",
    "            res += r - l + 1\n",
    "            r += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        start = -1\n",
    "        current_sum = 0\n",
    "        result = 0\n",
    "        for end in range(len(nums)):\n",
    "            current_sum += nums[end]\n",
    "            # if current_sum * (end - start) < k:  # 收缩\n",
    "            #     result += (end - start)\n",
    "            # else:  # 收缩\n",
    "            while end > start and current_sum * (end - start) >= k:\n",
    "                start += 1\n",
    "                current_sum -= nums[start]\n",
    "            result += (end - start)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 计算前缀和\n",
    "        sum = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            sum[i] = sum[i-1] + nums[i-1]\n",
    "        # 遍历手机答案\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            while i <= j:\n",
    "                score = (sum[j+1] - sum[i]) * (j-i+1)\n",
    "                if score < k:\n",
    "                    break\n",
    "                else:\n",
    "                    i += 1\n",
    "            ans += (j-i+1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# # \n",
    "# 【思路】\n",
    "# 1. 遍历每一个子数组，统计答案，可以使用前缀和优化，时间复杂度O(n^2)。n^2 过不了啊\n",
    "\n",
    "# 【伪码】\n",
    "# 1. 定义长度为 n+1 的数组sum表示前缀和数组，sum[n] 表示(0..n-1)的数组之和，那么计算 [i..j] 的和就为 sum[j+1] - sum[i]\n",
    "# 2. 定义变量ans，初始值为 0\n",
    "# 2. for i in range(0..n):\n",
    "#     for j in range(i..n):\n",
    "#     3. 计算[i..j]的分数：(sum[j+1] - sum[i]) * (j-i+1)\n",
    "#     4. 更新答案\n",
    "# 5. 返回答案\n",
    "# #  \n",
    "\n",
    "\n",
    "# 双指针是不行的 [1,2,3,4,5] => 10000\n",
    "\n",
    "# 5 + 4 + 3 + 2 + 1\n",
    "\n",
    "#  [i, j] 增加一个 j+1，那么结果增加 [j+1-i+1]. 如果不满足条件"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        res = [nums[0]] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = res[i-1] + nums[i]\n",
    "        return res\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        如果一个数组的分数小于k，则该数组的所有子数组都小于k\n",
    "        \"\"\"\n",
    "        presum = self.pre_sum(nums)\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        pre = 0\n",
    "        for right in range(len(nums)):\n",
    "            while (presum[right]-pre) * (right-left+1) >= k:\n",
    "                left += 1\n",
    "                pre = presum[left-1]\n",
    "            cnt += right-left+1 \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        s = [0] * (len(nums)+1)\n",
    "        for i in range(len(nums)):\n",
    "            s[i+1] = s[i]+nums[i]\n",
    "        return s\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        数组元素大于0\n",
    "        marks(i, j) = sum(i..j)*(j-i+1) = (p[j]-p[i-1])*(j-i+1)\n",
    "        故， marks(i, j) 关于 i 单调递减， 关于 j 单调递增，\n",
    "        假设marks(i, j)<k，而marks(i, j+1)>=k\n",
    "        对比子数组nums[i:j+1]和nums[i:j+1+1]，\n",
    "        后者比之前者，新增了j-i+1个子数组，\n",
    "        多出的部分是以nums[j+1]为右端点的所有数组，标记为j+1集合\n",
    "        通过left = left+1, 从j+1集合中剔除最大的元素，直到max(sets[j+1]) < k,\n",
    "        完成筛选，剩下的才是新增的满足条件的子数组，数量仍然为r-l+1\n",
    "        \n",
    "        总结就是：\n",
    "        通过右移左边界，直到新增子数组集合中的子数组最大值小于k，\n",
    "        \"\"\"\n",
    "        s = self.pre_sum(nums)\n",
    "        cnt = 0\n",
    "        l = 0\n",
    "        for r in range(1, len(s)):\n",
    "            # 从新增的子数组中筛选满足条件的\n",
    "            # s[j]-s[i] = sum(a[i:j])\n",
    "            while (s[r]-s[l])*(r-l) >= k:\n",
    "                l += 1\n",
    "            cnt += r-l\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1 ) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            s[i] = nums[i-1] + s[i-1]\n",
    "        print(s[n])\n",
    "\n",
    "        def check(arr, i):\n",
    "            nonlocal n\n",
    "            l, r = i, n-1\n",
    "\n",
    "            if (arr[n] - arr[i]) * (n - 1 - i + 1) < k:\n",
    "                #print(i, n-i)\n",
    "                return n - i\n",
    "\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if (arr[mid + 1] - arr[i]) * (mid - i + 1) >= k:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            #print(i, l - i)\n",
    "            return l - 1 - i + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            #print(check(s, i))\n",
    "            ans += check(s, i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right-left + 1) >= k :\n",
    "                s -= nums[left]\n",
    "                left += 1 \n",
    "            ans += right- left + 1\n",
    "\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "# count子数组\n",
    "# 接近滑窗思路"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        数组元素大于0\n",
    "        marks(i, j) = sum(i..j)*(j-i+1) = (p[j]-p[i-1])*(j-i+1)\n",
    "        故， marks(i, j) 关于 i 单调递减， 关于 j 单调递增，\n",
    "        假设marks(i, j)<k，而marks(i, j+1)>=k\n",
    "        对比子数组nums[i:j+1]和nums[i:j+1+1]，\n",
    "        后者比之前者，新增了j-i+1个子数组，\n",
    "        多出的部分是以nums[j+1]为右端点的所有数组，标记为j+1集合\n",
    "        通过left = left+1, 从j+1集合中剔除最大的元素，直到max(sets[j+1]) < k,\n",
    "        完成筛选，剩下的才是新增的满足条件的子数组，数量仍然为r-l+1\n",
    "        \n",
    "        总结就是：\n",
    "        通过右移左边界，直到新增子数组集合中的子数组最大值小于k，\n",
    "        \"\"\"\n",
    "        s = cnt = 0\n",
    "        l = 0\n",
    "        for r in range(len(nums)):\n",
    "            s += nums[r]\n",
    "            while s * (r - l + 1) >= k:\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            cnt += r-l+1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        l = 0\n",
    "        # 枚举右边界\n",
    "        for r, x in enumerate(nums):\n",
    "            # 剪枝, 这个右边界不可能成立\n",
    "            if x > k: \n",
    "                cur += x\n",
    "                continue\n",
    "            cur += x\n",
    "            # 找出最大滑窗(最靠左的左边界), 再小都满足了\n",
    "            while cur * (r - l + 1) >= k:\n",
    "                cur -= nums[l]\n",
    "                l += 1\n",
    "            # 从l到r的左边界都满足题意\n",
    "            if cur * (r - l + 1) < k:\n",
    "                ans += (r - l + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        su = nums[0]\n",
    "        ans = 0\n",
    "        for i, ni in enumerate(nums):\n",
    "            while j < n:\n",
    "                if su * (j - i + 1) < k:\n",
    "                    j += 1\n",
    "                    if j < n:\n",
    "                        su += nums[j]\n",
    "                else:\n",
    "                    break\n",
    "            ans += j - i\n",
    "            # print(i, ni, j, su, ans)\n",
    "            su -= nums[i]\n",
    "            # su -= nums[j]\n",
    "        \n",
    "            \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        l = ans = s = 0\n",
    "\n",
    "        for r, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (r - l + 1) >= k:\n",
    "                \n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            ans += (r - l + 1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        l = r = 0 \n",
    "        ksum = 0\n",
    "        kscore = 0 \n",
    "        ans = 0\n",
    "        while  r  <  len(nums):\n",
    "            num = nums[r]\n",
    "            r += 1\n",
    "            ksum += num\n",
    "            kscore = ksum * (r-l)\n",
    "            \n",
    "            while kscore >= k :\n",
    "                num = nums[l]\n",
    "                ksum -= num\n",
    "                l += 1\n",
    "                kscore = ksum *(r-l)\n",
    "                \n",
    "            \n",
    "            ans += r-l \n",
    "            \n",
    "\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "# count子数组\n",
    "# 接近滑窗思路？\n",
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        cur = 0\n",
    "        for r in range(n):\n",
    "            while (nums[r] + cur) * (r - l + 1) >= k:\n",
    "                ans += r - l\n",
    "                cur -= nums[l]\n",
    "                l += 1\n",
    "            cur += nums[r]\n",
    "        return ans+(n - l + 1) * (n - l ) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        left = ans = 0\n",
    "        s = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            s = (((s // (right - left)) if right != left else 0) + x) * (right - left + 1)\n",
    "            while s >= k:\n",
    "                s = ((s // (right - left + 1)) - nums[left]) * (right - left)\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans=s=left=0\n",
    "        for right,num in enumerate(nums):\n",
    "            s+=num\n",
    "            while s*(right-left+1)>=k:\n",
    "                s-=nums[left]\n",
    "                left+=1\n",
    "            ans+=right-left+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        res=cnt=l=r=0\n",
    "        n=len(nums)\n",
    "        while r<n:\n",
    "            cnt+=nums[r]\n",
    "            while cnt*(r-l+1)>=k:\n",
    "                cnt-=nums[l]\n",
    "                l+=1\n",
    "            res+=r-l+1\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        su = nums[0]\n",
    "        ans = 0\n",
    "        for i, ni in enumerate(nums):\n",
    "            while j < n and su * (j - i + 1) < k:\n",
    "                    j += 1\n",
    "                    if j < n:\n",
    "                        su += nums[j]\n",
    "            ans += j - i\n",
    "            # print(i, ni, j, su, ans)\n",
    "            su -= nums[i]\n",
    "            # su -= nums[j]\n",
    "        \n",
    "            \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        left = ans = 0\n",
    "        s = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            s += x\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        left=temp=res=0\n",
    "\n",
    "        for right in range(n):\n",
    "            temp+=nums[right]\n",
    "            while temp*(right-left+1)>=k:\n",
    "                temp-=nums[left]\n",
    "                left+=1\n",
    "            res+=right-left+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = r = 0\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        while r < n:\n",
    "            s += nums[r]\n",
    "            while s * (r - l + 1) >= k:\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            ans += r - l + 1\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        sum_val = 0\n",
    "        ans = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            sum_val += nums[right]\n",
    "            while sum_val * (right - left + 1) >= k:\n",
    "                sum_val -= nums[left]\n",
    "                left += 1\n",
    "            if sum_val * (right - left + 1) < k:\n",
    "               ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "      ans=s=l=0\n",
    "      for i,x in enumerate(nums):\n",
    "          s+=x\n",
    "          while s*(i-l+1)>=k:\n",
    "              s-=nums[l]\n",
    "              l+=1\n",
    "          ans+=i-l+1\n",
    "      return ans          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        s = [0] * (len(nums)+1)\n",
    "        for i in range(len(nums)):\n",
    "            s[i+1] = s[i]+nums[i]\n",
    "        return s\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        数组元素大于0\n",
    "        marks(i, j) = sum(i..j)*(j-i+1) = (p[j]-p[i-1])*(j-i+1)\n",
    "        故， marks(i, j) 关于 i 单调递减， 关于 j 单调递增，\n",
    "        如果一个数组的分数小于k，则该数组的所有子数组都小于k\n",
    "        枚举right端点，同时调整left端点，在线维护以j为右端点，分数小于k的数组\n",
    "        于是新的满足条件的子数组有right-left+1个\n",
    "        \"\"\"\n",
    "        s = self.pre_sum(nums)\n",
    "        cnt = 0\n",
    "        l = 1\n",
    "        for r in range(1, len(s)):\n",
    "            # 从新增的子数组中筛选满足条件的\n",
    "            while (s[r]-s[l-1])*(r-l+1) >= k:\n",
    "                l += 1\n",
    "            cnt += r-l+1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        sum =0\n",
    "        l=0\n",
    "        n =len(nums)\n",
    "        r=0\n",
    "        su=0\n",
    "        ge=0\n",
    "        for x in range(n):\n",
    "            su+=nums[x]\n",
    "            ge+=1\n",
    "            while su*ge>=k :\n",
    "                su-=nums[l]\n",
    "                l+=1\n",
    "                ge-=1\n",
    "            sum+=ge\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        j = 0\n",
    "        x, y = 0, 0\n",
    "        res = 0\n",
    "        nums.append(k)\n",
    "        for i in range(len(nums) - 1):\n",
    "            while x * y < k:\n",
    "                x += nums[j]\n",
    "                y += 1\n",
    "                j += 1\n",
    "            res += y - 1\n",
    "            x -= nums[i]\n",
    "            y -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        left, right = 0,0\n",
    "        window_sum = 0\n",
    "        while right<n:\n",
    "            window_sum += nums[right]\n",
    "            while window_sum*(right-left+1)>=k:\n",
    "                window_sum -= nums[left]\n",
    "                left+=1\n",
    "            res += (right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = count = 0\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            s += x\n",
    "            count += 1\n",
    "            while s * count >= k:\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "                count -= 1\n",
    "            ans += r - l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        l, res = 0, 0\n",
    "        total = 0\n",
    "        for r, n in enumerate(nums):\n",
    "            total += n\n",
    "            while total * (r - l + 1) >= k:\n",
    "                total -= nums[l]\n",
    "                l += 1\n",
    "            res += r - l + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0  # Initialize variables\n",
    "        for right, num in enumerate(nums):  # Loop through the array\n",
    "            s += num  # Update the sum of the current window\n",
    "            while s * (right - left + 1) >= k:  # Check if the condition is met\n",
    "                s -= nums[left]  # Remove the leftmost element from the sum\n",
    "                left += 1  # Move the left boundary to the right\n",
    "            ans += right - left + 1  # Update the answer\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        l = 0\n",
    "        # 枚举右边界\n",
    "        for r, x in enumerate(nums):\n",
    "            cur += x\n",
    "            # 找出最大滑窗(最靠左的左边界), 再小都满足了\n",
    "            while cur * (r - l + 1) >= k:\n",
    "                cur -= nums[l]\n",
    "                l += 1\n",
    "            # 从l到r的左边界都满足题意\n",
    "            ans += (r - l + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\r\n",
    "        ans = s = left = 0\r\n",
    "        for right, num in enumerate(nums):\r\n",
    "            s += num\r\n",
    "            while s * (right - left + 1) >= k:\r\n",
    "                s -= nums[left]\r\n",
    "                left += 1\r\n",
    "            ans += right - left + 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = s = left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s += num\n",
    "            while s * (right - left + 1) >= k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        left = right = 0\n",
    "        s = p = 0\n",
    "        ans = 0\n",
    "        while right <= len(nums) - 1:\n",
    "            p += nums[right]\n",
    "            s = p * (right - left + 1)\n",
    "            while left <= right and s >= k:\n",
    "                p -= nums[left]\n",
    "                left += 1\n",
    "                s = p * (right - left + 1)\n",
    "            if s < k:\n",
    "                ans += right - left + 1\n",
    "            right += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            s[i + 1] = s[i] + nums[i]\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for right, x in enumerate(nums, 1):\n",
    "            while (s[right] - s[left]) * (right - left) >= k:\n",
    "                left += 1\n",
    "            res += right - left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l,r = 0,0\n",
    "        fs,s,m = 0,0,0\n",
    "        res = 0\n",
    "        while r < len(nums):\n",
    "            # print(l,r,s,m,res)\n",
    "            if fs < k:\n",
    "                s += nums[r]\n",
    "                m += 1\n",
    "                fs = s * m\n",
    "                r += 1\n",
    "            else:\n",
    "                res += r-l-1\n",
    "                s -= nums[l]\n",
    "                m -= 1\n",
    "                fs = s * m\n",
    "                l += 1\n",
    "        while l < len(nums) and fs >= k:\n",
    "            res += r-l-1\n",
    "            s -= nums[l]\n",
    "            m -= 1\n",
    "            fs = s * m\n",
    "            l += 1\n",
    "        res += comb(r-l,2)+r-l\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        s = [0] * (len(nums)+1)\n",
    "        for i in range(len(nums)):\n",
    "            s[i+1] = s[i]+nums[i]\n",
    "        return s\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        数组元素大于0\n",
    "        marks(i, j) = sum(i..j)*(j-i+1) = (p[j]-p[i-1])*(j-i+1)\n",
    "        故， marks(i, j) 关于 i 单调递减， 关于 j 单调递增，\n",
    "        假设marks(i, j)<k，而marks(i, j+1)>=k\n",
    "        对比子数组nums[i:j+1]和nums[i:j+1+1]，\n",
    "        后者比之前者，新增了j-i+1个子数组，\n",
    "        多出的部分是以nums[j+1]为右端点的所有数组，标记为j+1集合\n",
    "        通过left = left+1, 从j+1集合中剔除最大的元素，直到max(sets[j+1]) < k,\n",
    "        完成筛选，剩下的才是新增的满足条件的子数组，数量仍然为r-l+1\n",
    "        \n",
    "        总结就是：\n",
    "        通过右移左边界，直到新增子数组集合中的子数组最大值小于k，\n",
    "        \"\"\"\n",
    "        s = self.pre_sum(nums)\n",
    "        cnt = 0\n",
    "        l = 1\n",
    "        for r in range(1, len(s)):\n",
    "            # 从新增的子数组中筛选满足条件的\n",
    "            while (s[r]-s[l-1])*(r-l+1) >= k:\n",
    "                l += 1\n",
    "            cnt += r-l+1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\r\n",
    "        window = 0\r\n",
    "        j = 0\r\n",
    "        n = len(nums)\r\n",
    "        res = 0\r\n",
    "        for i in range(n):\r\n",
    "            window += nums[i]\r\n",
    "            while window * (i - j + 1) >= k:\r\n",
    "                window -= nums[j]\r\n",
    "                j += 1\r\n",
    "            res += i - j + 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "            n = len(nums)\n",
    "            ans = 0\n",
    "            s = [0] * (n+1)\n",
    "            for i in range(n):\n",
    "                s[i+1] = s[i] + nums[i]\n",
    "            for i in range(1,n+1):\n",
    "                l,r = 1,i\n",
    "                while l < r:\n",
    "                    mid = l + r >> 1\n",
    "                    if (s[i] - s[mid-1]) * (i - mid + 1) < k:\n",
    "                        r = mid\n",
    "                    else:l = mid + 1\n",
    "                # print(l,i,(s[i] - s[l-1]) * (i - l + 1) )\n",
    "                if (s[i] - s[l-1]) * (i - l + 1) < k:\n",
    "                    ans += i - l + 1\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        diff, right, res = [0], 0, 0\n",
    "        for x in nums:\n",
    "            diff.append(diff[-1] + x)\n",
    "        for left in range(len(nums)):\n",
    "            right = max(left, right)\n",
    "            while right < len(nums) and (diff[right + 1] - diff[left]) * (right - left + 1) < k:\n",
    "                right += 1\n",
    "            res += right - left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums, initial = 0))\n",
    "        j = ans = 0\n",
    "        for i in range(n):\n",
    "            while True:\n",
    "                s = pre[i+1] - pre[j]\n",
    "                d = i - j + 1\n",
    "                if s * d < k:\n",
    "                    break\n",
    "                j += 1\n",
    "            ans += i - j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n=len(nums)\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        for i in range(n):\n",
    "            tosub = acc[i]\n",
    "            j = bisect_left(range(i,n), k, key=lambda x:(x-i+1)*(acc[x+1]-tosub))\n",
    "            ans += j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\r\n",
    "        # 滑窗 or 二分\r\n",
    "        # 滑窗 296 ms \r\n",
    "        s = list(accumulate(nums, initial=0))\r\n",
    "        # res = cur = 0 \r\n",
    "        # l = 0 \r\n",
    "        # for i, x in enumerate(nums):\r\n",
    "        #     cur = (s[i + 1] - s[l]) * (i - l + 1)\r\n",
    "        #     while cur >= k:\r\n",
    "        #         l += 1\r\n",
    "        #         cur = (s[i + 1] - s[l]) * (i - l + 1)\r\n",
    "        #     res += i - l + 1 \r\n",
    "        # return res \r\n",
    "\r\n",
    "\r\n",
    "        # 二分 \r\n",
    "        res = 0 \r\n",
    "        for i in range(len(nums)):\r\n",
    "            l, r = -1, i + 1\r\n",
    "            while l + 1 < r :\r\n",
    "                mid = (l + r) // 2 \r\n",
    "                if (s[i + 1] - s[mid]) * (i - mid + 1) < k:\r\n",
    "                    r = mid \r\n",
    "                else:\r\n",
    "                    l = mid\r\n",
    "            res += i - r + 1 \r\n",
    "        return res  \r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\r\n",
    "        s = list(accumulate(nums, initial=0))\r\n",
    "        res = 0\r\n",
    "        for right in range(len(nums)):\r\n",
    "            l, r = -1, right + 1\r\n",
    "            while l + 1 < r:\r\n",
    "                # \r\n",
    "                mid = (l + r) // 2\r\n",
    "                if (s[right + 1] - s[mid]) * (right - mid + 1) < k:\r\n",
    "                    r = mid\r\n",
    "                else:\r\n",
    "                    l = mid\r\n",
    "            res += right - r + 1\r\n",
    "        return res \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        pre_sm = list(accumulate(nums, initial=0))\n",
    "        ans = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            while left<=right and (right-left+1) * (pre_sm[right+1]-pre_sm[left]) >= k:\n",
    "                left+=1\n",
    "            ans += right-left+1\n",
    "            \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
